#include <stdio.h>
#include <iostream>
#include <utility>
#include <string>
#include <stack>
#include <climits>

using namespace std;

const int COST_MAX = 2000000000;

class Solucion{
  int cost;
  stack <pair<int,int> > posiciones;

 public:
  Solucion();
  ~Solucion();
  Solucion(stack<pair<int,int> > posiciones, int cost);
  stack <pair<int,int> > get_Pposiciones()const;
  pair<int,int> get_posicion()const;  //RECORDAR necesario hacer pop
  int get_cost()const;
  int size_posiciones()const;
  bool empty_posiciones()const;
  void set_posicion(pair<int,int> posicion_v);
  void set_cost(int cost_v);
  void pop_posicion();
  void copiar(Solucion sol_c);
  bool cortar(pair<int,int> p_corte, int** mapa);
  void concatenar_sol(stack <pair<int,int> > posiciones_c);
  pair<int,int> cortar(int num_nodos, int** mapa);
  Solucion vecina(int n_pos, int** mapa,int* max_dim);
  Solucion vecina2(int pos1, int pos2, int **mapa);
  Solucion vecina3(int pos1, int pos2, int **mapa);
  Solucion vecina4(int pos1, int pos2, int **mapa);
  void toString()const;
  void Print_pos();
  void P4plot_coste();
};

Solucion::Solucion(){
  cost = COST_MAX;
}

Solucion::Solucion(stack<pair<int,int> > posiciones_v, int cost_v){
  posiciones = posiciones_v;
  cost = cost_v;
}

stack <pair<int,int> > Solucion::get_Pposiciones()const{
  return posiciones;
}
pair<int,int> Solucion::get_posicion()const{ //RECORDAR necesario hacer pop
  return posiciones.top();
}

int Solucion::get_cost()const{
  return cost;
}

int Solucion::size_posiciones()const{
  return posiciones.size();
}

bool Solucion::empty_posiciones()const{
  return posiciones.empty();
}

void Solucion::set_posicion(pair<int,int> posicion_v){
  posiciones.push(posicion_v);
}

void Solucion::set_cost(int cost_v){
  cost = cost_v;
}

void Solucion::pop_posicion(){
  posiciones.pop();
}

bool Solucion::cortar(pair<int,int> p_corte, int** mapa){
  stack <pair<int,int> > pila_aux;
  int coste_aux=0;
  bool encontrado = false;
  while(!encontrado && !posiciones.empty()){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    if(posiciones.top() == p_corte)
      encontrado=true;
    posiciones.pop();
  }
  while(!posiciones.empty()) //vaciar pila
    posiciones.pop();

  //formamos la solucion con el nuevo coste y pila de posiciones
  cost = coste_aux;
  while (!pila_aux.empty()){
    posiciones.push(pila_aux.top());
    pila_aux.pop();
  }
  return encontrado; //será falso si la posicion no pertenece a sol
}

void Solucion::concatenar_sol(stack <pair<int,int> > posiciones_c){
  stack <pair<int,int> > pila_aux;
  while(!posiciones.empty()) {
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }
  posiciones_c.pop();//posición repetida
  while(!posiciones_c.empty()){
    pila_aux.push(posiciones_c.top());
    posiciones_c.pop();
  }
  while(!pila_aux.empty()){
    posiciones.push(pila_aux.top());
    pila_aux.pop();
  }
}

void Solucion::copiar(Solucion sol_c){
  //stack <pair<int,int> > pila_aux;
  //pila_aux = sol_c.get_Pposiciones();
  //while (!pila_aux.empty()){
  posiciones=sol_c.get_Pposiciones();
  //pila_aux.pop();
  // aux = posiciones.top();

  cost = sol_c.get_cost();
}

/* dado un entero dejará la solución con ese número de nodos */
pair<int,int> Solucion::cortar(int num_nodos, int **mapa){
  stack <pair<int,int> > pila_aux;
  pair<int,int> pos_ret;
  int i = 0;
  int coste_aux=0;

  pair<int,int> aux;
  for(i=0; i<num_nodos;i++){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }
  while(!posiciones.empty()) //vaciar pila
    posiciones.pop();
  /* formamos la solucion con el nuevo coste y pila de posiciones */
  pos_ret = pila_aux.top();
  cost = coste_aux;
  while (!pila_aux.empty()){
    posiciones.push(pila_aux.top());
    pila_aux.pop();
    aux = posiciones.top();
  }
  return pos_ret;
}

bool en_pila(stack <pair<int,int> > pila_in, int x, int y){
  bool ret_en = false;

  while (!pila_in.empty()){
    if(pila_in.top().first == x and pila_in.top().second == y)
      ret_en = true;
    pila_in.pop();
  }

  return ret_en;
}

int alternativ(pair<int,int> ant, pair<int,int> cent, pair<int,int> post){
  int op_ret = 0;

  if(ant.first==cent.first-1 and post.first==cent.first+1 and
     ant.second==cent.second and post.second==cent.second)
    op_ret = 1;

  if(ant.first==cent.first and post.first==cent.first and
     ant.second==cent.second-1 and post.second==cent.second+1)
    op_ret = 2;

  if(ant.first==cent.first-1 and post.first==cent.first and
     ant.second==cent.second and post.second==cent.second+1)
    op_ret = 3;

  if(ant.first==cent.first and post.first==cent.first+1 and
     ant.second==cent.second-1 and post.second==cent.second)
    op_ret = 4;

  if(ant.first==cent.first-1 and post.first==cent.first and
     ant.second==cent.second and post.second==cent.second-1)
    op_ret = 5;

  if(ant.first==cent.first and post.first==cent.first+1 and
     ant.second==cent.second+1 and post.second==cent.second)
    op_ret = 6;

  return op_ret;
}


Solucion Solucion::vecina4(int pos1, int pos2, int **mapa){
  Solucion sol_ret;
  pair<int,int> p1,p2;
  stack <pair<int,int> > pila_aux,pila_recu;
  int i, x, y, x1,x2,y1,y2, coste_aux=0;

  pila_recu = posiciones;

  //guardamos parte de antes del pto modificado
  for (i=0; i<pos1;i++){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }
  //primer punto:
  x1=posiciones.top().first;
  y1=posiciones.top().second;
  posiciones.pop();
  //eliminamos desde pos1 a pos2
  for (i=pos1; i<pos2;i++)
    posiciones.pop();
  //segundo punto:
  x2=posiciones.top().first;
  y2=posiciones.top().second;
  posiciones.pop();
  //calculamos los puntos entre p1 y p2 angulo dcho
  y =y1;
  if(x1<x2){
    for (x=x1; x<=x2; x++){
      coste_aux += mapa[x][y];
      pila_aux.push(make_pair(x,y));
    }
  }
  else{
    for (x=x1; x>=x2; x--){
      coste_aux += mapa[x][y];
      pila_aux.push(make_pair(x,y));
    }
  }

  if(y1<y2){
    for (y=y1+1; y<=y2; y++){
      coste_aux += mapa[x2][y];
      pila_aux.push(make_pair(x2,y));
    }
  }
  else{
    for (y=y1-1; y>=y2; y--){
      coste_aux += mapa[x2][y];
      pila_aux.push(make_pair(x2,y));
    }
  }

  //guardamos el resto
  while(!posiciones.empty()){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }

  sol_ret.set_cost(coste_aux); //guardamos toda la nueva sol
  while(!pila_aux.empty()){
    sol_ret.set_posicion(pila_aux.top());
    pila_aux.pop();
  }

  posiciones = pila_recu;
  return sol_ret;
}


Solucion Solucion::vecina3(int pos1, int pos2, int **mapa){
  Solucion sol_ret;
  pair<int,int> p1,p2;
  stack <pair<int,int> > pila_aux,pila_recu;
  int i, x, y, x1,x2,y1,y2, coste_aux=0;

  pila_recu = posiciones;

  //guardamos parte de antes del pto modificado
  for (i=0; i<pos1;i++){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }
  x1=posiciones.top().first;
  y1=posiciones.top().second;
  posiciones.pop();
  //eliminamos desde pos1 a pos2
  for (i=pos1; i<pos2;i++){
    posiciones.pop();
  }
  x2=posiciones.top().first;
  y2=posiciones.top().second;
  posiciones.pop();
  //calculamos los puntos entre p1 y p2 angulo izq
  x =x1;
  if(y1<y2){
    for (y=y1; y<=y2; y++){
      coste_aux += mapa[x][y];
      pila_aux.push(make_pair(x,y));
    }
  }
  else{
    for (y=y1; y>=y2; y--){
      coste_aux += mapa[x][y];
      pila_aux.push(make_pair(x,y));
    }
  }

  if(x1<x2){
    for (x=x1+1; x<=x2; x++){
      coste_aux += mapa[x][y2];
      pila_aux.push(make_pair(x,y2));
    }
  }
  else{
    for (x=x1-1; x>=x2; x--){
      coste_aux += mapa[x][y2];
      pila_aux.push(make_pair(x,y2));
    }
  }

  //guardamos el resto
  while(!posiciones.empty()){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }

  sol_ret.set_cost(coste_aux); //guardamos toda la nueva sol
  while(!pila_aux.empty()){
    sol_ret.set_posicion(pila_aux.top());
    pila_aux.pop();
  }

  posiciones = pila_recu;
  return sol_ret;
}


Solucion Solucion::vecina2(int pos1, int pos2, int **mapa){
  Solucion sol_ret;
  stack <pair<int,int> > pila_aux,pila_recu;
  int i, x, y, x1,x2,y1,y2, coste_aux=0;

  pila_recu = posiciones;

  //guardamos parte de antes del pto modificado
  for (i=0; i<pos1;i++){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }
  x1=posiciones.top().first;
  y1=posiciones.top().second;

  posiciones.pop();
  //eliminamos desde pos1 a pos2
  for (i=pos1; i<pos2;i++){
    posiciones.pop();
  }
  x2=posiciones.top().first;
  y2=posiciones.top().second;
  posiciones.pop();
  //calculamos los puntos entre p1 y p2 Bresenham

  int deltax = x2 - x1;
  if(deltax !=0){
    int deltay = y2 - y1;
    float error_bre = 0;
    float deltaerr = abs(deltay / deltax);
    y = y1;
    for (x=x1; x<=x2; x++){
      coste_aux += mapa[x][y];
      pila_aux.push(make_pair(x,y));
      error_bre = error_bre + deltaerr;
      if (error_bre >= 0.5){
	y = y + 1;
	coste_aux += mapa[x][y];
	pila_aux.push(make_pair(x,y));
	error_bre = error_bre - 1.0;
      }
    }

    while(y2>=y){
      coste_aux += mapa[x2][y];
      pila_aux.push(make_pair(x2,y));
      y++;
    }

    //guardamos el rest
    while(!posiciones.empty()){
      coste_aux += mapa[posiciones.top().first][posiciones.top().second];
      pila_aux.push(posiciones.top());
      posiciones.pop();
    }

    sol_ret.set_cost(coste_aux); //guardamos toda la nueva sol
    while(!pila_aux.empty()){
      sol_ret.set_posicion(pila_aux.top());
      pila_aux.pop();
    }
  }
  else // deltax =0
    sol_ret.set_cost(COST_MAX);

  posiciones = pila_recu;
  return sol_ret;
}

Solucion Solucion::vecina(int n_pos, int** mapa, int *max_dim){
  Solucion sol_ret;
  pair<int,int> anterior,elim,posterior;
  stack <pair<int,int> > pila_aux,pila_recu;
  int i, auxX, auxY, expand, coste_aux=0;

  pila_recu = posiciones;


  //guardamos parte de antes del pto modificado
  for (i=0; i<n_pos-1;i++){
    coste_aux += mapa[posiciones.top().first][posiciones.top().second];
    pila_aux.push(posiciones.top());
    posiciones.pop();
  }
  //pos ante
  anterior = posiciones.top();
  posiciones.pop();
  //pos a eliminar
  elim = posiciones.top();
  posiciones.pop();

  auxX = elim.first;
  auxY = elim.second;

  posterior = posiciones.top();
  posiciones.pop();

  //calculamos las nuevas posciones hasta la pos post
  expand = alternativ(anterior,elim,posterior);

  if(expand!=0){
    switch(expand){
    case 1: //. x .  => .   .
            //          . . .
      if (auxY+1<max_dim[1]){
	if(!en_pila(pila_recu, auxX-1,auxY+1)){
	  coste_aux += mapa[anterior.first][anterior.second];
	  pila_aux.push(anterior);
	  coste_aux += mapa[auxX-1][auxY+1];
	  pila_aux.push(make_pair(auxX-1,auxY+1));
	}

	coste_aux += mapa[auxX][auxY+1];
	pila_aux.push(make_pair(auxX,auxY+1));

	if(!en_pila(pila_recu, auxX+1,auxY+1)){
	  coste_aux += mapa[auxX+1][auxY+1];
	  pila_aux.push(make_pair(auxX+1,auxY+1));
	  coste_aux += mapa[posterior.first][posterior.second];
	  pila_aux.push(posterior);
	}
      }else if(auxY-1>0){ //          . . .
	                  //. x .  => .   .
	if(!en_pila(pila_recu, auxX-1,auxY-1)){
	  coste_aux += mapa[anterior.first][anterior.second];
	  pila_aux.push(anterior);
	  coste_aux += mapa[auxX-1][auxY-1];
	  pila_aux.push(make_pair(auxX-1,auxY-1));
	}
	coste_aux += mapa[auxX][auxY-1];
	pila_aux.push(make_pair(auxX,auxY-1));

	if(!en_pila(pila_recu, auxX+1,auxY-1)){
	  coste_aux += mapa[auxX+1][auxY-1];
	  pila_aux.push(make_pair(auxX+1,auxY-1));
	  coste_aux += mapa[posterior.first][posterior.second];
	  pila_aux.push(posterior);
	}
      }

      break;
    case 2: //.      . .
            //x  =>    .
            //.      . .
      if(auxX+1<max_dim[0]){
	if(!en_pila(pila_recu, auxX+1,auxY+1)){
	  coste_aux += mapa[anterior.first][anterior.second];
	  pila_aux.push(anterior);
	  coste_aux += mapa[auxX+1][auxY-1];
	  pila_aux.push(make_pair(auxX+1,auxY-1));
	}

	coste_aux += mapa[auxX+1][auxY];
	pila_aux.push(make_pair(auxX+1,auxY));
	if(!en_pila(pila_recu, auxX+1,auxY+1)){
	  coste_aux += mapa[auxX+1][auxY+1];
	  pila_aux.push(make_pair(auxX+1,auxY+1));
	  coste_aux += mapa[posterior.first][posterior.second];
	  pila_aux.push(posterior);
	}
      }
      else if(auxX-1>0){    //.      . .
                            //x  =>  .
                            //.      . .
	if(!en_pila(pila_recu, auxX-1,auxY-1)){
	  coste_aux += mapa[anterior.first][anterior.second];
	  pila_aux.push(anterior);
	  coste_aux += mapa[auxX-1][auxY-1];
	  pila_aux.push(make_pair(auxX-1,auxY-1));
	}
	coste_aux += mapa[auxX-1][auxY];
	pila_aux.push(make_pair(auxX-1,auxY));
	if(!en_pila(pila_recu, auxX-1,auxY+1)){
	  coste_aux += mapa[auxX-1][auxY+1];
	  pila_aux.push(make_pair(auxX-1,auxY+1));
	  coste_aux += mapa[posterior.first][posterior.second];
	  pila_aux.push(posterior);
	}
      }
      break;
    case 3: //. x  =>  .
            //  .      . .
      coste_aux += mapa[anterior.first][anterior.second];
      pila_aux.push(anterior);
      coste_aux += mapa[auxX-1][auxY+1];
      pila_aux.push(make_pair(auxX-1,auxY+1));
      coste_aux += mapa[posterior.first][posterior.second];
      pila_aux.push(posterior);
      break;
    case 4: //.    =>  . .
            //x .        .
      coste_aux += mapa[anterior.first][anterior.second];
      pila_aux.push(anterior);
      coste_aux += mapa[auxX+1][auxY-1];
      pila_aux.push(make_pair(auxX+1,auxY-1));
      coste_aux += mapa[posterior.first][posterior.second];
      pila_aux.push(posterior);
      break;
    case 5: //  .  =>  . .
            //. x      .
      coste_aux += mapa[anterior.first][anterior.second];
      pila_aux.push(anterior);
      coste_aux += mapa[auxX-1][auxY-1];
      pila_aux.push(make_pair(auxX-1,auxY-1));
      coste_aux += mapa[posterior.first][posterior.second];
      pila_aux.push(posterior);
      break;
    case 6: //x .  =>   .
            //.       . .
      coste_aux += mapa[anterior.first][anterior.second];
      pila_aux.push(anterior);
      coste_aux += mapa[auxX+1][auxY+1];
      pila_aux.push(make_pair(auxX+1,auxY+1));
      coste_aux += mapa[posterior.first][posterior.second];
      pila_aux.push(posterior);
      break;
    default: cout<<"ERROR EN CALCULO DE VECINA"<<endl;
      break;
    }

    //seguimos guardando el resto de sol
    while(!posiciones.empty()){
      coste_aux += mapa[posiciones.top().first][posiciones.top().second];
      pila_aux.push(posiciones.top());
      //pila_recu.push(posiciones.top());
      posiciones.pop();
    }

    sol_ret.set_cost(coste_aux); //guardamos toda la nueva sol
    while(!pila_aux.empty()){
      sol_ret.set_posicion(pila_aux.top());
      pila_aux.pop();
    }
  }//end if expand!=0
  else{
    sol_ret.set_cost(COST_MAX);
  }

  posiciones = pila_recu;

  return sol_ret;
}



void Solucion::toString()const{
  cout << "Nodos totales: " << posiciones.size() << " coste: "<< cost << endl;
}

void Solucion::Print_pos(){
  stack <pair<int,int> > pila_aux;
  cout<< "Print_pos: "<<endl;
  while(!posiciones.empty()){
    pila_aux.push(posiciones.top());
    cout << posiciones.top().first<<"  "<< posiciones.top().second<<endl;
    posiciones.pop();
  }
  while(!pila_aux.empty()){
    posiciones.push(pila_aux.top());
    pila_aux.pop();
  }
}

void Solucion::P4plot_coste(){
  cout << cost << endl;
}

Solucion::~Solucion(){
}
